package com.cuz.daileetcode.avl;

import java.util.Objects;
import java.util.Optional;

/**
 * @author cuzz
 * @version 1.0
 * @description: AVL 树
 * @date 20:23 2022/2/5
 **/
public class AVLTree<T extends Comparable<T>, V> {

    private AVLTreeNode<T, V> rootNode;

    /**
     * 获取当前树高度
     * 如果根节点不为null 返回根节点属性 height的值
     * 否则返回0
     *
     * @return 树高度
     */
    public int height() {
        return height(rootNode);
    }


    private int height(AVLTreeNode<T, V> node) {
        return Optional.ofNullable(node)
                .map(AVLTreeNode::getHeight)
                .orElse(0);
    }

    /**
     * 重新刷新节点的高度
     * 如果节点为null 那么什么都不做
     * 如果左右儿子为null 自己不为null 设置高度为1
     * 反之 将左右子树的高度刷新，父节点的高度为左右子树高度最大值+1
     *
     * @param node 需要刷新高度的节点
     * @return 当前节点的高度
     */
    private int reloadHeight(AVLTreeNode<T, V> node) {
        if (node == null) {
            return height(null);
        }
        if (Objects.isNull(node.getLeft())
                && Objects.isNull(node.getRight())) {
            node.setHeight(1);
            return height(node);
        }
        reloadHeight(node.getLeft());
        reloadHeight(node.getRight());
        int lHeight = height(node.getLeft());
        int rHeight = height(node.getLeft());
        node.setHeight(Math.max(lHeight, rHeight) + 1);
        return height(node);
    }

    private int reloadHeight() {
        return reloadHeight(rootNode);
    }

    /***
     * 左左旋
     * 由于左树过长而导致失去了平衡
     * @param node
     * @return 返回调整后新的头节点
     */
    private AVLTreeNode<T, V> leftLeftRotation(AVLTreeNode<T, V> node) {
        AVLTreeNode<T, V> newRootNode = node.getLeft();
        AVLTreeNode<T, V> newRootRightTree = newRootNode.getRight();
        newRootNode.setRight(node);
        node.setLeft(newRootRightTree);
        return newRootNode;
    }

    /***
     * 右右旋
     * 由于右 树过长而导致失去了平衡
     * @param node
     * @return 返回调整后新的头节点
     */
    private AVLTreeNode<T, V> rightRightRotation(AVLTreeNode<T, V> node) {
        AVLTreeNode<T, V> newRootNode = node.getRight();
        AVLTreeNode<T, V> newRootLeftTree = newRootNode.getLeft();
        newRootNode.setLeft(node);
        node.setRight(newRootLeftTree);
        return newRootNode;
    }

    /***
     * 左右旋
     * 由于左树右儿子过长而导致失去了平衡
     * @param node
     * @return 返回调整后新的头节点
     */
    private AVLTreeNode<T, V> leftRightRotation(AVLTreeNode<T, V> node) {
        node.setLeft(rightRightRotation(node.getLeft()));
        return leftLeftRotation(node);
    }

    /***
     * 右左旋
     * 由于右树左儿子过长而导致失去了平衡
     * @param node
     * @return 返回调整后新的头节点
     */
    private AVLTreeNode<T, V> rightLeftRotation(AVLTreeNode<T, V> node) {
        node.setRight(leftLeftRotation(node.getRight()));
        return rightRightRotation(node);
    }

    /***
     * 重新建立父子关系
     * 父>node ===> node 为 左子树
     * 父<node ===> node 为 右子树
     * @param parent 父亲节点
     * @param node 需要建立关系的节点
     */
    private void claimPSConnect(AVLTreeNode<T, V> parent, AVLTreeNode<T, V> node) {
        int compareRes = parent.getKey().compareTo(node.getKey());
        if (compareRes > 0) {
            //父亲大于node 那么说明 是左树
            parent.setLeft(node);
        } else if (compareRes < 0) {
            parent.setRight(node);
        } else {
            throw new UnsupportedOperationException("不符合构建父子节点关系的标准");
        }
    }

    /**
     * 重新调整为平衡的树
     *
     * @param node 平衡操作的起点
     *             1.插入节点，新插入的节点造成了树的不平衡
     *             从插入节点开始，向上检查以当前节点为根节点的树是否平衡，如果不平衡那么进行平衡操作
     *             2.除节点，从删除节点影响的节点开始检查起
     *             如果删除的是叶子节点，那么是父节点受到了影响，从父节点开始检查
     *             如果删除的是存在子节点，但是不送左右双全，这时候子节点会替换被删除节点，从替换后的节点检查起
     *             如果删除的节点左右儿子双全，那么从替换后的节点检查起
     */
    private void balanceAgain(AVLTreeNode<T, V> node) {
        if (Objects.isNull(node)) {
            return;
        }
        while (node != null) {
            AVLTreeNode<T, V> parent = node.getParent();
            int leftHeight = height(node.getLeft());
            int rightHeight = height(node.getRight());
            int heightDiff = rightHeight - leftHeight;
            if (heightDiff == 2) {
                //LL型
                if (node.getRight().getRight() == null) {
                    node = leftLeftRotation(node);
                } else {
                    //RL型
                    node = rightLeftRotation(node);
                }
                claimPSConnect(parent, node);
                break;
            } else if (heightDiff == -2) {
                //rr型
                if (node.getLeft().getLeft() == null) {
                    node = rightRightRotation(node);
                } else {
                    //RL型
                    node = leftRightRotation(node);
                }
                claimPSConnect(parent, node);
                break;
            } else {
                reloadHeight(node);
                node = parent;
            }
        }
        reloadHeight();
    }

}
